Rappresentazione NAF
La rappresentazione NAF (dall'inglese non-adjacent form - rappresentazione non adiacente) di un numero è una rappresentazione binaria unica di cifre con segno, in cui i valori diversi da zero non possono essere adiacenti. Ad esempio:
- (0 1 1 1)2 = 4 + 2 + 1 = 7
- (1 0 −1 1)2 = 8 − 2 + 1 = 7
- (1 −1 1 1)2 = 8 − 4 + 2 + 1 = 7
- (1 0 0 −1)2 = 8 − 1 = 7
Tutte sono rappresentazioni valide di 7 in cifre con segno, ma solo l'ultima rappresentazione, (1 0 0 −1)2 è in forma non adiacente.
Proprietà[modifica | modifica wikitesto]
NAF assicura una rappresentazione unica di un numero intero, ma il suo principale vantaggio è che il peso di Hamming del valore sarà minimo. Nella rappresentazione binaria dei numeri, in media la metà di tutti i bit sarà diversa da zero, ma con la rappresentazione NAF questo valore scende mediamente ad un terzo di tutte le cifre. Ciò porta a implementazioni efficienti di circuiti di addizione/sottrazione impiegati nell'elaborazione di segnali digitali.[1]
Ovviamente, al massimo la metà delle cifre è diversa da zero, che è il motivo per cui è stata introdotta da G.W. Reitweisner [2] per velocizzare i primi algoritmi di moltiplicazione, in modo simile all'algoritmo di Booth.
Poiché ogni cifra diversa da zero deve essere adiacente a due 0, la rappresentazione NAF può essere implementata in modo tale da richiedere al massimo m + 1 bit per un valore che normalmente sarebbe rappresentato in binario con m bit.
Le proprietà di NAF lo rendono utile in vari algoritmi, in particolare nell'ambito della crittografia; ad esempio, per ridurre il numero di moltiplicazioni necessarie per eseguire il calcolo di una potenza. Nell'algoritmo dell'elevamento a potenza per quadratura, il numero di moltiplicazioni dipende dal numero di bit diversi da zero. Se l'esponente viene dato in rappresentazione NAF, il valore 1 implica una moltiplicazione per la base, e il valore −1 per il suo reciproco.
Altre modalità di codifica degli interi che evitano sequenze consecutive di 1 includono l'algoritmo di Booth e la codifica di Fibonacci.
Note[modifica | modifica wikitesto]
- ^ R.M. Hewlitt, Canonical signed digit representation for FIR digital filters, Signal Processing Systems, 2000. SiPS 2000. 2000 IEEE Workshop on, 2000, pp. 416–426, DOI:10.1109/SIPS.2000.886740, ISBN 978-0-7803-6488-2.
- ^ George W. Reitwiesner, Binary Arithmetic, in Advances in Computers, vol. 1, 1960, pp. 231–308, DOI:10.1016/S0065-2458(08)60610-5, ISBN 9780120121014.
